/*
 *  hash.hpp - hash table template
 *
 *    Copyright (c) 2001-2006, Luxena Software Company. All rights reserved.
 *
 *  Purpose:
 *
 */

#ifndef __HASH_HPP__
#define __HASH_HPP__

#ifndef __cplusplus
#error This header requires a C++ compiler ...
#endif

#include <new>
#include <memory.h>


/////////////////////////////////////////////////////////////////////////////
// HashTable - hash table template class

template <typename Key, typename Value, class Comparer>
class HashTable
{
public:
	struct Element
	{
		Key key;
		Value value;

	private:
		Element *_next;
		friend class HashTable;
		friend class Iterator;
	};

	typedef Element* Chain;

	class Iterator
	{
	public:
		Iterator()
		{
			_currentElement = 0;
		}

		Iterator& operator ++()
		{
			if (_currentElement != 0)
				_SetElement(_currentElement->_next);
			return *this;
		}

		Iterator operator ++(int)
		{
			Chain *startChain = _currentChain;
			Chain *lastChain = _lastChain;
			if (_currentElement != 0)
				_SetElement(_currentElement->_next);
			return Iterator(startChain, lastChain);
		}

		Element* operator ->()
		{
			return _currentElement;
		}

		operator Element*()
		{
			return _currentElement;
		}

	private:
		friend class HashTable;

		void _SetElement(Element *element)
		{
			while (element == 0 && _currentChain != _lastChain)
				element = *++_currentChain;
			_currentElement = element;
		}

		Iterator(Chain *startChain, Chain *lastChain)
		{
			_currentChain = startChain;
			_lastChain = lastChain;
			_SetElement(*_currentChain);
		}

		Chain *_currentChain;
		Chain *_lastChain;
		Element *_currentElement;
	};


	HashTable(unsigned int size)
	{
		_size = 0;
		(_chains = 0) = new Chain [size];
		memset(_chains, 0, size*sizeof(Chain));
		_size = size;
		_count = 0;
	}

	~HashTable()
	{
		clear();
		delete [] _chains;
	}

	Element* add(const Key& key)
	{
		Chain *chain = &_chains[Comparer::GetHashCode(key, _size)];

		Element *element = new Element;
		element->_next = *chain;
		*chain = element;
		_count++;
		element->key = key;

		return element;
	}

	Element* put(const Key& key)
	{
		Chain *chain = &_chains[Comparer::GetHashCode(key, _size)];

		Element *element;

		while ((element = *chain) != 0)
		{
			if (Comparer::Compare(element->key, key) == 0)
				return element;
			chain = &element->_next;
		}
	
		element = new Element;
		element->_next = 0;
		*chain = element;
		_count++;
		element->key = key;

		return element;
	}

	Element* get(const Key& key)
	{
		Element *element = _chains[Comparer::GetHashCode(key, _size)];

		while (element != 0)
		{
			if (Comparer::Compare(element->key, key) == 0)
				return element;
			element = element->_next;
		}

		return 0;
	}

	void * remove(const Key& key)
	{
		Chain *chain = &_chains[Comparer::GetHashCode(key, _size)];

		Element *element;

		while ((element = *chain) != 0)
		{
			if (Comparer::Compare(element->key, key) == 0)
			{
				Element *nextElement = element->_next;
				delete element;
				_count--;
				*chain = nextElement;
				return element;
			}
			chain = &element->_next;
		}

		return 0;
	}

	void clear()
	{
		Chain *chain = _chains;

		for (unsigned int i = 0; i < _size; i++, chain++)
		{
			Element *element;
			while ((element = *chain) != 0)
			{
				Element *nextElement = element->_next;
				delete element;
				_count--;
				*chain = nextElement;
			}
		}
	}

	Iterator begin()
	{
		return Iterator(_chains, &_chains[_size - 1]);
	}

	Iterator end()
	{
		return Iterator();
	}

	unsigned long count()
	{
		return _count;
	}

private:
	unsigned int _size;
	Chain *_chains;
	unsigned int _count;
};

#endif // __HASH_HPP__
